package outoforder.leetcode;

import java.util.HashMap;
import java.util.HashSet;

/**
 * @author shhjiang_001
 * @create 2020-07-06 14:04
 */
public class Solution887 {
    HashMap<String, Integer> map = new HashMap<>();
    public int superEggDrop1(int K, int N) {
        return dpMethod(K,N);
    }
    int dpMethod(int K, int N){
        if(K==1) return N;
        if(N==0) return 0;
        if (map.containsKey(K+"_"+N)){
            return map.get(K+"_"+N);
        }
        int res = Integer.MAX_VALUE;
        for (int i = 1; i < N+1; i++) {
            res = Math.min(res,Math.max(dpMethod(K,N-i),dpMethod(K-1,i-1))+1);
        }
        map.put(K+"_"+N,res);
        return res;
    }
    public int superEggDrop(int K, int N) {
        int[][] dp = new int[K + 1][N + 1];
        int m = 0;
        while (dp[K][m]< N){
            m++;
            for (int i = 1; i <= K; i++) {
                dp[i][m] = dp[i][m-1] + dp[i-1][m-1]+1;
            }

        }
        return m;
    }
}
